Ánh xạ giữa hai tập sắp thứ tự một phần Tập hợp sắp thứ tự một phần

Hình 7a. Ánh xạ này bảo toàn thứ tự nhưng không phản xạ thứ tự (vì f(u) ≼ f(v), nhưng không u ≤ {\displaystyle \leq } v).
Hình 7b. Đẳng cấu thứ tự giữa các ước số của 120 (sắp thứ tự một phần theo tính chia hết) và tập con của {2, 3, 4, 5, 8} (sắp thứ tự một phần theo quan hệ chứa trong)

Cho hai tập hợp sắp thứ tự một phần (S, ≤) và (T, ≼),[lower-alpha 3] hàm f : S → T {\displaystyle f:S\to T} được gọi là bảo toàn thứ tự, đơn điệu, hoặc đẳng điệu, nếu với mọi x , y ∈ S , {\displaystyle x,y\in S,} x ≤ y {\displaystyle x\leq y} suy ra f(x) ≼ f(y).Nếu (U, ≲) cũng là tập sắp thứ tự một phần và cả hai hàm f : S → T {\displaystyle f:S\to T} và g : T → U {\displaystyle g:T\to U} đều bảo toàn thứ tự thì hàm hợp g ∘ f : S → U {\displaystyle g\circ f:S\to U} cũng bảo toàn thứ tự.Hàm f : S → T {\displaystyle f:S\to T} được gọi là phản xạ thứ tự nếu với mọi x , y ∈ S , {\displaystyle x,y\in S,} f(x) ≼ f(y) suy ra x ≤ y . {\displaystyle x\leq y.} Nếu f {\displaystyle f} vừa bảo toàn thứ tự vừa phản xạ thứ tự thì nó được gọi là phép nhúng thứ tự của (S, ≤) vào (T, ≼).Trong trường hợp này, f {\displaystyle f} phải là đơn ánh, vì f ( x ) = f ( y ) {\displaystyle f(x)=f(y)} suy ra x ≤ y  và  y ≤ x {\displaystyle x\leq y{\text{ và }}y\leq x} và do vậy x = y {\displaystyle x=y} theo tính phản đối xứng của ≤ . {\displaystyle \leq .} Nếu tồn tại phép nhúng thứ tự giữa hai tập sắp thứ tự một phần S và T, ta có thể nói S được nhúng vào T. Nếu phép nhúng thứ tự f : S → T {\displaystyle f:S\to T} là song ánh. thì nó được gọi là đẳng cấu thứ tự và hai thứ tự một phần (S, ≤) và (T, ≼) được gọi là đẳng cấu với nhau. Quan hệ thứ tự đẳng cấu với nhau có cấu trúc biểu đồ Hasse tương tự với nhau (xem hình 7a). Ta có thể chứng minh nếu tồn tại hai ánh xạ bảo toàn thứ tự f : S → T {\displaystyle f:S\to T} và g : T → U {\displaystyle g:T\to U} sao cho cả hai g ∘ f {\displaystyle g\circ f} và f ∘ g {\displaystyle f\circ g} đều là hàm đồng nhất trên S và T, tương ứng, thì S và T đẳng cấu thứ tự với nhau.[15]

Ví dụ, xét hàm f : N → P ( N ) {\displaystyle f:\mathbb {N} \to \mathbb {P} (\mathbb {N} )} từ tập hợp các số tự nhiên (xếp theo tính chia hết) tới tập lũy thừa của các số tự nhiên (xếp theo quan hệ chứa trong) có thể được định nghĩa bằng cách ánh xạ mỗi số sang tập các ước nguyên tố của số đó. Nó bảo toàn thứ tự vì nếu x {\displaystyle x} là ước của y , {\displaystyle y,} thì mỗi ước nguyên tố của x {\displaystyle x} cũng là ước nguyên tố của y . {\displaystyle y.} Tuy nhiên, nó không phải đơn ánh (vì nó ánh xạ cả 12 và 6 sang { 2 , 3 } {\displaystyle \{2,3\}} ) và cũng không phản xạ thứ tự (vì 12 không phải là ước của của 6). Nếu thay vì đó, định nghĩa ánh xạ mỗi số sang tập các ước lũy thừa nguyên tố của nó qua g : N → P ( N ) {\displaystyle g:\mathbb {N} \to \mathbb {P} (\mathbb {N} )} ánh xạ này bảo toàn thứ tự, phản xạ thứ tự và do đó là phép nhúng thứ tự. Song, nó không phải đẳng cấu thứ tự (Bởi vì , ví dụ chẳng hạn nó không ánh xạ số nào sang tập { 4 } {\displaystyle \{4\}} ), tuy nhiên nó có thể trở thành một bằng cách giới hạn miền giá trị thành g ( N ) . {\displaystyle g(\mathbb {N} ).} Hình 7b minh họa một tập hợp con của N {\displaystyle \mathbb {N} } và ảnh dưới phép đẳng cấu g . {\displaystyle g.} Cách xây dựng đẳng cấu thứ tự vào tập lũy thừa này có thể tổng quát hóa cho một lớp rộng rãi các quan hệ thứ tự một phần, được gọi là dàn phân phối, xem "định lý biểu diễn Birkhoff".

Liên quan

Tài liệu tham khảo

WikiPedia: Tập hợp sắp thứ tự một phần http://dml.cz/dmlcz/142762 http://match.stanford.edu/reference/combinat/sage/... http://www.eecs.umich.edu/courses/eecs203-1/203-Ma... //hdl.handle.net/10338.dmlcz%2F101379 //doi.org/10.1090%2FS0002-9939-1954-0063016-5 //doi.org/10.1090%2FS0002-9939-1968-0236071-7 //oeis.org/A001035 https://books.google.com/books?id=66oqDAAAQBAJ&q=%... https://books.google.com/books?id=6i-F3ZNcub4C&pg=... https://books.google.com/books?id=vVVTxeuiyvQC&pg=...